A component included in all computing devices is memory. A device's main memory (e.g., RAM, flash, etc.) provides storage that can be quickly written to and read from by a processor. Main memory is allocated to an operating system and programs during runtime (throughout the duration of execution). When a program terminates, memory allocated to that program is freed (de-allocated), and may subsequently be allocated to a different program.
There are multiple conventional memory allocation schemes by which memory can be allocated and de-allocated. One standard conventional memory allocation scheme is heap memory allocation.
FIG. 1 illustrates a block diagram of a conventional heap-based memory allocation 100. The heap based memory allocation 100 consists of a heap 105 having a single arena 110 from which memory can be allocated. The illustrated arena 110 includes a first metadata structure 115, first memory block 120, second metadata structure 125, second memory block 130, third metadata structure 135, and third memory block 140. As illustrated, in heap based memory allocation, a memory block is always preceded by a metadata structure associated with that memory block. The metadata structure includes a header that describes the size of the associated memory block or a pointer to a subsequent metadata structure. As illustrated, first metadata structure 115 includes a pointer that points to second metadata structure 125, and second metadata structure 125 includes a pointer that points to third metadata structure 135.
To find an unallocated block of memory, metadata structures must be navigated until a metadata structure is discovered that is associated with a memory block that has sufficient capacity to satisfy an allocation request. On average, half of the unallocated metadata structures need to be examined before a suitable memory block is discovered. This can impair system performance.
When allocating memory blocks, mistakes can be made by a program that uses allocated memory such that data is written to subsequent metadata structures and/or memory blocks. This may cause portions of the subsequent metadata structures and/or memory block to be overwritten, commonly referred to as an overrun bug or buffer overrun. When subsequent metadata structures are overwritten, information about the associated memory block can be lost, and information about subsequent metadata structures can be lost. This loss of information may cause a program to crash the next time a memory allocation or de-allocation request is made.
When a memory allocation is requested, but there are not sufficient available memory blocks, memory blocks may be freed by moving data from the main memory to secondary memory (e.g., to a hard disk) in a process referred to as paging. For paging to operate, main memory is divided into a series of equally sized memory pages 145. The size of the memory pages 145 depends on the architecture on which the main memory is located. For example, in the x86 architecture of most personal computers (PCs), each memory page is 4 kilobytes (4,096 bytes). To free main memory, memory pages 145 are transferred as a unit into secondary storage (e.g., hard disk, optical storage, other magnetic media).
Referring to FIG. 1, the heap 105 includes a plurality of memory pages 145. In the conventional heap-based memory allocation, as in other conventional memory allocation schemes, there is no alignment between memory pages 145 and assigned memory blocks, data structures, or arenas. Therefore, when memory blocks are moved to secondary memory, some portions of memory blocks and/or data structures may remain in the primary memory, and other portions of these memory blocks and/or data structures may be moved to secondary memory. This may significantly impact system performance.
Many modern operating systems support the ability for multiple threads and processes to be run concurrently. However, only a single thread may actually be active at a time per processor core of a computing device. Where multiple threads are run concurrently, the operating system switches back and forth between operative threads. If an active thread is switched to inactive during memory allocation, the switch may occur after a memory block has been allocated, but before an associated data structure has been updated. If the new active thread makes a memory allocation, it may allocate the same memory block that the previously active thread allocated, since the data structure does not yet reflect the fact that the memory block has already been allocated. When the first thread next becomes active, it finishes its memory allocation and updates the data structure associated with the memory block that it had previously allocated. As a result, the data structure no longer accurately describes the size of the memory block, nor does it accurately point to the next data structure. This may cause both threads to crash.
To mitigate the above mentioned problem, conventional memory allocation schemes provide locks to guarantee that only a single thread can be allocated a specific memory block. However, conventional memory allocators must lock out an entire arena of memory during allocation to assure that appropriate memory blocks are locked. Thus, only a single thread can allocate memory at a time, causing other threads to wait, and severely impacting system performance.